Mobile multi-hop broadcast packet radio networks are known for their rapid and convenient deployment, self organization, mobility, and survivability. In this type of network as illustrated in FIG. 1, a transmission from one node, for example node 1, is broadcast to all nodes in its “neighborhood”. Ultra-high frequency (UHF) systems generally have a neighborhood defined by nodes within line of sight of the transmitting node (these nodes being termed within one “hop” of the transmitting node). For example, in FIG. 1 nodes 1, 3, 4, 5, 6, 7, and 8 make up one neighborhood. For data transmitted from node 1 to propagate multiple hops, the data must be relayed by one or more of node 1's neighbors. For example, node “a” (likewise nodes b, c, and g) is two hops away from the node 1 transmitter. The data will be relayed in this manner until it has arrived at all intended destination nodes.
Collisions can generally be avoided by the assignment of time slots in which individual nodes can transmit because a typical receiver can only successfully process a single transmission. Various approaches can decide which nodes are assigned which slots. The approach is generally driven by the network applications, such as broadcast, multicast, unicast, datagrams, virtual circuits, etc. Because the problem of optimally assigning slots in this environment is mathematically intractable, a heuristic approach is taken to design an integrated protocol that both chooses the number of slots to assign to each neighboring node and coordinates their activation in the network.
Traditionally, there are two primary types of channel access schemes. The first, known in the literature as “node activation”, depicted in FIG. 2, has a transmitter broadcast to all of its neighbors at once rather than individually. When a transmitter has only one intended receiver it is known as “link activation”, depicted in FIG. 3. The former allows only one active transmitter in a neighborhood while the latter can potentially have several.
Node activation is especially well suited for broadcast messages like those used for address resolution. Link activation, on the other hand, lends itself better to high volume point-to-point traffic where allocations are made along the path of the traffic for the duration of a session. Thus, mobile multi-hop broadcast packet radio networks may use a hybrid network using node activations for low volume control traffic and occasional datagrams and link activations for high volume point-to-point traffic.
The Unifying Slot Assignment Protocol (USAP), which is the subject of U.S. Pat. No. 5,719,868 is a practical method to facilitate the implementation of the node and link activations in wireless networks.
When a node chooses an allocation, USAP enforces certain constraints to avoid interference within 2 hops of the transmitter. For link activation from node i to neighbor j, it must be an allocation:                that has not already been assigned to either node;        that i's neighbors are not receiving in; and        that j's neighbors are not transmitting in.For node activation, a node i must choose an allocation:        that has not already been assigned to node i or any of its neighbors; and                    none of i's neighbors' neighbors are transmitting in.                        
To achieve higher efficiency, it might be desirable to allow multiple transmitters in a neighborhood to share the same slot to utilize it more effectively. One such channel access technique would have the nodes sharing a slot simply take turns transmitting in the slot. This is easy to implement and scales to arbitrarily large groups sharing the same slot (albeit at the expense of arbitrarily large latencies.) Such a channel access technique has the drawback of requiring large overhead and is not significantly efficient.
Also, to achieve higher efficiency, it might be desirable to allow multiple transmitters in a neighborhood to share the same slot and to apply a number of higher level heuristics, such as those described in U.S. application Ser. No. 09/303,528 entitled Unifying Slot Assignment Protocol Multiple Access, which is herein incorporated by reference.
Thus, there is a need and desire for an alternative to USAP node allocation. There is also a need and desire for a USAP node allocation alternative that allows time slots to be shared among neighboring nodes.